package org.leetcode.middle.leetcode416;

public class Solution2 {
    public static void main(String[] args) {
        int [] test = {1,5,11,5};

        boolean b = canPartition(test);
        System.out.println(b);
    }
    public static boolean canPartition(int[] nums) {
        int sum = 0;

        for (int num:nums) {
            sum+=num;
        }

        if (sum%2!=0){
            return false;
        }

        int target = sum/2;

        int [] dp = new int[target+1];
        dp[0]=0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >=nums[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }

        return dp[target]==target;
    }
}
